This invention relates to the formatting of digital data into a pattern, encoding that pattern onto a substrate where appropriate, and decoding that pattern to reconstruct the digital data.
While computers have substantially enhanced the manner in which society conveys and works with information, paper remains the favored manner of conveying information. Indeed, the proliferation of personal computers has resulted in a proliferation of paper. Yet, no technology to date has significantly integrated the digital environment of the computer with the visual environment of written media. Instead, computers primarily direct human readable information to be placed on paper.
It would be greatly advantageous to have digital data placed on paper and other media currently used for human readable information. Such a method would link the largely separate environments of paper and computers. The method could store and convey digital data with greater efficiency, ease, speed, and lesser cost than any other available method. The method would have the further advantage of being the only significant method to integrate digital data with visual media.
As described below, the prior art discloses methods for placing machine readable information on media such as paper. However, none of these prior art methods, and, to the best of the inventors' knowledge, no other technology currently available to personal computer users allows for the placement of a significant amount of machine readable information on the media. Other practical limitations of these prior art methods forestall significant commercial success.
One example of digital information being stored on paper is the use of bar codes. Because standard bar codes are one dimensional, they are severely limited in the number of bars that may be used to store digital information. The limits are somewhat greater in the case of two-dimensional bar codes but these limits are still far more restrictive than the theoretical limits of any particular printer, and bar codes are designed for use with specialized scanners. For more information on bar codes, see "Information Encoding with Two-Dimensional Bar Codes," authored by T. Pavlidis, J. Schwartz and Y. Wang, COMPUTER, June 1992.
U.S. Pat. No. 5,245,165, issued to Zhang, discloses a self-clocking glyph code for encoding dual bit digital values of a logically ordered sequence of wedge-shaped glyphs that are written or otherwise recorded on a hardcopy recording medium in accordance with a predetermined spatial formatting rule. The dual bit values are encoded in the relative rotations of the glyphs. The glyphs are decoded by determining a bounding box for each glyph and determining either which quadrant of the box contains its center of mass or by comparing the relative locations of the shortest and longest runs of ON pixels. To reliably present a single bit of data, each glyph comprises a large number of pixels, and thus this technology requires considerable space on the recording medium. The technology does not optimize the use of space or computational resources by presenting a bit in the most compact fashion.
U.S. Pat. No. 5,337,362, issued to Gormish, discloses a method for transferring digital information to and from plain paper. The method involves storing data in at least one box on the paper, the box including a frame or border having alternating pixels along the left and right edges for use in determining the current location of a horizontal line of pixels when reading the data and having pixels in corners of the frame to determine horizontal spacing between pixels within the box. Binary data is formatted in rows within the box, wherein a bit of digital data is depicted by the presence or absence of an ink dot. The method disclosed by Gormish provides the ability to represent 60 kilobytes of data on a single page.
Although Gormish allows for the storage of more data on a page than can currently be stored in text form, it has several problems which prevent it from being useful in a commercial environment. For example, Gormish requires a thick frame to be placed around the entire data box in order to locate the box, which limits the ability to place the data in convenient shapes and sizes on a substrate. Also, Gormish requires placement of pixels in a rigid fashion, without provision of guideposts to determine where to search for the presence or lack of a dot other than on the borders of the boxes. Further, Gormish provides ink placement in an ink dot that covers an entire square and that square covers an area 16 times larger than the finest optical resolution of any given scanner (e.g., Gormish discloses printing dots at 50 dpi while scanning is performed at 200 dpi), thereby limiting the density of data which can be represented on each page. In addition, although the method disclosed in Gormish may be suited for certain printers and scanners of great precision it does not adequately accommodate for deviations from perfection in printing and scanning found in off-the-shelf printers and scanners designed for use with personal computers. Operating in an environment of personal computers and their peripherals, this rigidity ultimately translates into loss of data density, higher error rates, slower processing speed, all of these deficiencies, or, worse yet, complete inability to use the method in given computer environments.
Other known methods disclose manners in which a single cell contains more than one bit of information through the use of gray scales. One such method is disclosed in U.S. Pat. No. 5,278,400, issued to J. Appel (1994). This patent discloses the encoding of multiple bits in a single cell by marking, preferably by binary marking, a predetermined number of pixels in a cell irrespective of the location of the pixels within the cell. The number of pixels marked corresponds to the data to be encoded. The markings on the substrate are decoded by detecting the gray scale level at each pixel of the cell, converting that gray scale level to a corresponding digital signal and summing all of the digital signals corresponding to all of the pixels in the cell. This method requires discrete determination of where the cell begins and ends. The gains from encoding multiple values in a single cell are lost by requiring larger cells, relative to straightforward binary printing. Gormish also discloses the encoding of multiple values in one cell through the use of gray scale inks. This method employs rigid formatting and printing described above and similarly relies on rigid decoding mechanisms that may be optimized for a particular combination of a printer and a scanner, but not for all such combinations. These methods give back the data density and savings in computational resources that the use of multiple colors should provide.
U.S. Pat. No. 5,329,107, issued to D. Priddy and R. Cymbalski (1994), discloses a method to dynamically vary the size, format, and density of machine readable binary code. The method disclosed in that document provides a code formed of a matrix and allows variation in the amount of data in the matrix by printing on two sides of the perimeter of the matrix broken line patterns of alternating darkened and lightened areas. The method determines the amount of data in the matrix from the product of the number of lightened areas and darkened areas of the first side and the number of lightened areas and darkened areas of the second. The method determines size of the matrix by measuring the other two sides of the perimeter, formed of two solid black lines. While the method allows the encoder of information some flexibility in accommodating the different potentials of higher and lower resolution scanners, the method is rigid in darkening entire square cells. The method also lacks regular reference markers and generally limits information about the encoding, conveyed in the matrix, to size and density. The method therefore lacks the flexibility needed to address the peculiarities of every combination of printer and scanner. Hence the method can not produce the greatest density of data or the most efficient manner of decoding for every combination of printer and scanner.
There is a need to substantially increase the amount of data that can be stored within a given amount of paper in order to compete with other channels of storage and communication such as floppy disks and digital communication by telephone. Employing binary printing (i.e., storing one bit per cell), the most basic and least dense printing process, the invention is capable of storing data at densities several times as great as any other paper based method known to the inventors. Utilizing printing methods which store more than one bit per cell, such as color printing, the theoretical density limits increase substantially.
While Gormish discloses the ability to store 60 kilobytes on a single page using a 400 dpi scanner, the invention is capable of encoding and decoding over 160 kilobytes of data error free (i.e., by utilizing error correction) using just a 300 dpi scanner. With the aid of compression, this single page can contain over 500 kilobytes of text. With a 600 dpi printer and a 600 dpi flatbed scanner, the invention can encode data in cells 1/200 inch square (i.e., 0.005 inch.times.0.005 inch), successfully encoding and decoding over 300 kilobytes of data before the benefit of any compression, in excess of 1 megabyte of text with the aid of compression. Utilizing more precise printing processes and a 600 dpi flatbed scanner, the invention encodes and decodes over 7,000 bytes per square inch (over 1,100 bytes/cm.sup.2), over 20,000 bytes of text using compression. Utilizing an ordinary thermal fax machine as a scanner (achieving a binary scan of approximately 200 dpi), the invention encodes and decodes over 50 kilobytes of data, over 150 kilobytes of text with the aid of compression. All of the above densities are accomplished utilizing binary printing.
The invention also conveys advantages for any particular printer. For example, using an ordinary thermal fax machine the invention can print over 230 kilobytes of data, over 675 kilobytes of text with compression, on an 8.5 by 11 in. piece of thermal fax paper. The invention can then successfully decode that data error free.